package 数据结构练习;

import java.util.ArrayList;
import java.util.List;

public class 归并排序 {
    public static void main(String[] args) {
        int a[] = new int[]{5,9,6,7,3,1,2,4,8};
        sort(a,0,a.length-1);
        for(int x:a){
            System.out.print(x+" ");
        }
    }

    //递归方法，l和r代表当前递归的左右边界
    public static void sort(int[] a,int l,int r){
        //判断越界
        if(l<0 || r>=a.length || l>=r){
            return;
        }
        int top=l,tail=(l+r)/2+1;
        //临时链表，用于临时存储排序后的数据
        List<Integer> temp = new ArrayList<>();
        //将当前区域平分成两块
        sort(a,l,tail-1);
        sort(a,tail,r);
        //将排好序的左右两部合并进行排序
        while (top!=(l+r)/2+1 || tail!=r+1){
            //左边已经取完
            if(top == (l+r)/2+1){
                while (tail!=r+1){
                    temp.add(a[tail]);
                    tail++;
                }
            }
            //右边已经取完
            else if(tail == r+1){
                while (top!=(l+r)/2+1){
                    temp.add(a[top]);
                    top++;
                }
            }
            //若都有剩余，就进行比较，哪个小取哪个
            else{
                if(a[top]<a[tail]){
                    temp.add(a[top]);
                    top++;
                }
                else {
                    temp.add(a[tail]);
                    tail++;
                }
            }
        }
        //将临时链表的数据填回数组中
        for(int x:temp){
            a[l] = x;
            l++;
        }
    }
}
